package com.sqi.algorithm.structure;

import java.util.Random;
import java.util.Stack;

/**
 * 带有最小值的栈
 *
 * @Author sqi
 * @Date 2021/6/8
 * @Version V1.0.0
 **/
public class MinStackTest {
    public static void main(String[] args) {
        int max = 50;
        MinStack minStack = new MinStack();
        Random random = new Random();
        for (int i = 0; i < max; i++) {
            minStack.push(random.nextInt(max));
        }
        minStack.print();
        for (int i = 0; i < max; i++) {
            System.out.println("Pop:" + minStack.pop() + ", Min value is:" + minStack.minValue());
        }
    }

    private static class MinStack {
        private final Stack<Integer> valueStack = new Stack<Integer>();
        private final Stack<Integer> minValueStack = new Stack<Integer>();

        public void push(Integer value) {
            valueStack.push(value);
            if (minValueStack.isEmpty() || minValueStack.peek() >= value) {
                minValueStack.push(value);
            }
        }

        public Integer pop() {
            Integer value = valueStack.pop();
            if (value.equals(minValueStack.peek())) {
                minValueStack.pop();
            }
            return value;
        }

        public Integer minValue() {
            if (minValueStack.isEmpty()) {
                return null;
            }
            return minValueStack.peek();
        }

        public void print() {
            System.out.println(valueStack.toString());
            System.out.println(minValueStack.toString());

        }
    }
}
